package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T00120 {
    public static void main(String[] args) {
        // [[2],[3,4],[6,5,7],[4,1,8,3]]
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));
        System.out.println(new Solution().minimumTotal(triangle));
    }

    static class Solution {
        private static final int MAX_VALUE = 999999;
        private static final int CACHE_VALUE = 888888;
        private int[][] cache;
        public int minimumTotal(List<List<Integer>> triangle) {
            int lastIndex = triangle.size() - 1;
            List<Integer> lastRow = triangle.get(lastIndex);
            cache = new int[lastIndex + 1][lastIndex + 1];
            for (int[] c : cache) {
                Arrays.fill(c, CACHE_VALUE);
            }
            int res = MAX_VALUE;
            for (int i = 0; i < lastRow.size(); i ++) {
                res = Math.min(res, dp(triangle, lastIndex, i));
            }
            return res;
        }

        public int dp(List<List<Integer>> triangle, int i, int j) {
            if (i < 0 || i >= triangle.size()) return MAX_VALUE;
            if (i == 0) return triangle.get(0).get(0);
            List<Integer> curRow = triangle.get(i);
            if (j < 0 || j >= curRow.size()) return MAX_VALUE;
            if (cache[i][j] != CACHE_VALUE) {
                return cache[i][j];
            }
            int minVal = curRow.get(j) + Math.min(dp(triangle, i - 1, j), dp(triangle, i - 1, j - 1));
            cache[i][j] = minVal;
            return minVal;
        }
    }
}
